#include <iostream>
#include <stack>
#include <stdlib.h>

using namespace std;

struct ListNode
{
    int m_nValue;
    ListNode * m_pNext;
};

ListNode * CreateListNode(int value)
{
    ListNode * pNode = new ListNode();
    pNode->m_nValue = value;
    pNode->m_pNext = NULL;

    return pNode;
}

void ConnectListNodes(ListNode * pCurrent, ListNode * pNext)
{
    if(pCurrent == NULL)
    {
        cout << "Error to connect two nodes" << endl;
        exit(1);
    }
    pCurrent->m_pNext = pNext;
}

void PrintListNode(ListNode * pNode)
{
    if(pNode == NULL)
    {
        cout << "The node is NULL" << endl;
    }
    else
    {
        cout << "The key in node is " << pNode->m_nValue;
    }
}

void PrintList(ListNode * pHead)
{
    cout << "PrintList starts" << endl;
    ListNode * pNode = pHead;
    while(pNode != NULL)
    {
        cout << pNode->m_nValue << " ";
        pNode = pNode->m_pNext;
    }
    cout << "\nPrintList ends" << endl;
}

void DestoryList(ListNode * pHead)
{
    ListNode * pNode = pHead;
    while (pNode != NULL)
    {
        pHead = pHead->m_pNext;
        delete pNode;
        pNode = pHead;
    }
}

void AddToTail(ListNode **  pHead, int value)
{
    ListNode * pNew = new ListNode();
    pNew->m_nValue = value;
    pNew->m_pNext = NULL;
    if(*pHead == NULL)
    {
        *pHead = pNew;
    }
    else
    {
        ListNode * pNode = *pHead;
        while(pNode->m_pNext != NULL)
        {
            pNode = pNode->m_pNext;
        }
        pNode->m_pNext = pNew;
    }
}

void RemoveNode(ListNode ** pHead, const int value)
{
    if (NULL == pHead || NULL == *pHead)
        return;

    ListNode * pToBeDeleted = NULL;
    if ((*pHead)->m_nValue == value)
    {
        pToBeDeleted = *pHead;
        *pHead = (*pHead)->m_pNext;
    }
    else
    {
        ListNode * pNode = *pHead;
        while(pNode->m_pNext != NULL && pNode->m_pNext->m_nValue != value)
            pNode = pNode->m_pNext;
        if (pNode->m_pNext != NULL && pNode->m_pNext->m_nValue == value)
        {
            pToBeDeleted = pNode->m_pNext;
            pNode->m_pNext = pNode->m_pNext->m_pNext;
        }
    }
    if (pToBeDeleted != NULL)
    {
        delete pToBeDeleted;
        pToBeDeleted = NULL;
    }
}

// 从尾到头打印链表
void PrintListReversingly_Iteratively(ListNode * pHead)
{
    std::stack<ListNode *> nodes;
    ListNode * pNode = pHead;
    while(pNode != NULL)
    {
        nodes.push(pNode);
        pNode = pNode->m_pNext;
    }
    while(!nodes.empty())
    {
        pNode = nodes.top();
        cout << pNode->m_nValue << " ";
        nodes.pop();
    }
    cout << endl;
}

void PrintListReversingly_Recurisively(ListNode * pHead)
{
    if(pHead != NULL)
    {
        if (pHead->m_pNext != NULL)
        {
            PrintListReversingly_Recurisively(pHead->m_pNext);
        }
        cout << pHead->m_nValue << " ";
    }
}

// 在O(1)时间删除链表结点
// 给定单向链表的头指针和一个结点指针，定义一个函数在O(1)时间删除该结点。
// 思路：采用pToBeDeleted结点的后一个结点的值替换掉该结点
void DeleteNode(ListNode ** pListHead, ListNode * pToBeDeleted)
{
    if (pListHead == NULL || pToBeDeleted == NULL)
        return;

    // 删除的结点不是尾结点
    if (pToBeDeleted->m_pNext != NULL)
    {
        ListNode * pNext = pToBeDeleted->m_pNext;
        pToBeDeleted->m_nValue = pNext->m_nValue;
        pToBeDeleted->m_pNext = pNext->m_pNext;

        delete pNext;
        pNext = NULL;
    }
    // 链表只有一个结点，删除头结点(也是尾结点)
    else if(*pListHead == pToBeDeleted)
    {
        delete pToBeDeleted;
        pToBeDeleted = NULL;
        *pListHead = NULL;
    }
    // 删除的结点是尾结点
    else
    {
        ListNode * pNode = *pListHead;
        while (pNode->m_pNext != pToBeDeleted)
            pNode = pNode->m_pNext;
        
        pNode->m_pNext = NULL;
        delete pToBeDeleted;
        pToBeDeleted = NULL;
    }
}

// 循环反转链表
ListNode * ReverseList_Iteratively(ListNode * pListHead)
{
    if (pListHead == NULL)
        return NULL;
    ListNode * pReverseHead = NULL;
    ListNode * pNode = pListHead;
    ListNode * pPreNode = NULL;
    while (pNode != NULL)
    {
        ListNode * pNext = pNode->m_pNext;
        if(pNext == NULL)
            pReverseHead = pNode;
        
        // 防止链表断裂
        pNode->m_pNext = pPreNode;
        
        pPreNode = pNode;
        pNode = pNext;
    }
    return pReverseHead;
}

// 递归反转链表
ListNode * ReverseList_Recursively(ListNode * pListHead)
{
    // 递归的终止条件，找到链表的最后一个结点
    if (pListHead == NULL || pListHead->m_pNext == NULL)
        return pListHead;
    ListNode * pReversedListHead = ReverseList_Recursively(pListHead->m_pNext); // 先反转后面的链表，从最后的两个结点开始反转，依次向前
    cout << pListHead << endl;
    pListHead->m_pNext->m_pNext = pListHead;     // 后一个链表结点指向前一个结点
    pListHead->m_pNext = NULL;                   // 断开原链表中前一个结点指向后一个结点的指向关系
    return pReversedListHead;
}
